/* Exercise 5.37
   This is a implementation of Hanoi Towers, iterative solution
   probably I will use more things that chapter 5 give us
   ejer5_37.c */
#include <stdio.h>
#include <stdlib.h>

/* type definition */
/* This struct will represent a Towert */
struct tower
{
    int *disks;
    int index;
    int name;
    int size;
}; /* end struct tower */

typedef struct tower Tower;

/* function prototypes */
void hanoi(int orig, int aux, int destiny, int n);
void createEmptyTower(Tower *theTower, int size, int name);
void destroyTower(Tower *theTower);
int readFirstDisk(const Tower theTower);
int getFirstDisk(Tower *theTower);
int isTheTowerEmpty(const Tower theTower);
void putDiskOnTower(Tower *theTower, int element);

/* function main begins program execution */
int main( void )
{
    int disks;

    printf("Enter the number of the disks: ");
    scanf("%d", &disks);

    hanoi(1, 2, 3, disks);
	return 0; /* indicate that program ended successfully */
} /* end function main */

/* hanoi function */
void hanoi(int orig, int aux, int destiny, int n)
{
    Tower towers[3];
    int i, j, direction, index;
    int firstDiskMoved;

    createEmptyTower(&towers[0], n, orig);
    createEmptyTower(&towers[1], n, aux);
    createEmptyTower(&towers[2], n, destiny);

    /* Put all the disks on tower 1 */
    for (i = n; i >= 1; i--)
        putDiskOnTower(&towers[0], i);

    i = 0;
    if ( n % 2 == 0)
        direction = 1;
    else
        direction = -1;

    while(towers[2].index < n - 1)
    {
        /* First find a tower with a odd disk */
        firstDiskMoved = 0;
        for (j = 1; j < 3 && firstDiskMoved == 0; j++)
        {
            index = (i + j) % 3;

            if (!isTheTowerEmpty(towers[index]))
            {
                if (readFirstDisk(towers[index]) % 2 == 0)
                {
                    putDiskOnTower(&towers[index], getFirstDisk(&towers[i]));

                    printf("%d -> %d\n", towers[i].name, towers[index].name);
                    i = index;
                    firstDiskMoved = 1;
                }
            }
        }

        /* In case that the firstDisk hasn't moved yet then search the next Empty disk */
        if (firstDiskMoved == 0)
        {
            index = i + direction;

            if ( index < 0 )
                index = (3 + index % 3) % 3;
            else
                index = index % 3;
            putDiskOnTower(&towers[index], getFirstDisk(&towers[i]));

            printf("%d -> %d\n", towers[i].name, towers[index].name);
            i = index;
            firstDiskMoved = 1;
        }

        /* In case that the game isn't finished then move another disk */
        if (towers[2].index < n - 1)
        {
            int smallest = 0,
                greatest = 0;

            for (j = 0; j < 3; j++)
            {
                int disk = readFirstDisk(towers[j]);

                if ( disk > readFirstDisk(towers[greatest]))
                    greatest = j;
                if ((disk < readFirstDisk(towers[smallest]) && disk != 1) || readFirstDisk(towers[smallest]) == 1)
                    smallest = j;
            }

            putDiskOnTower(&towers[greatest], getFirstDisk(&towers[smallest]));
            printf("%d -> %d\n", towers[smallest].name, towers[greatest].name);
        }
    }

    destroyTower(&towers[0]);
    destroyTower(&towers[1]);
    destroyTower(&towers[2]);
}

/* Creates a empty tower */
void createEmptyTower(Tower *theTower, int size, int name)
{
    theTower->disks = malloc(size * sizeof(int));
    theTower->index = -1;
    theTower->name = name;
    theTower->size = size;
} /* end function createEmptyTower */

/* Destroys a tower */
void destroyTower(Tower *theTower)
{
    free(theTower->disks);
} /* end function destroyTower */

/* reads the First disk on the tower, if it is empty, returns n + 1 */
int readFirstDisk(const Tower theTower)
{
    if (isTheTowerEmpty(theTower))
        return theTower.size + 1;
    return theTower.disks[theTower.index];
} /* end function readFirstDisk */

/* reads the First disk and drops from the Tower */
int getFirstDisk(Tower *theTower)
{
    int disk = theTower->disks[theTower->index];

    --theTower->index;

    return disk;
} /* end function getFirstDisk */

/* return true if the Tower is empty */
int isTheTowerEmpty(const Tower theTower)
{
    return theTower.index == -1;
} /* end function isTheTowerEmpty */

/* put on the Tower a disk */
void putDiskOnTower(Tower *theTower, int element)
{
    ++theTower->index;
    theTower->disks[theTower->index] = element;
} /* end function putDiskOnTower */
